package org.zhenhu.CSCE310.StrassenMatrix;


import java.util.Arrays;

import Jama.Matrix;


public class StrassenMatrix {


		
		public Matrix strassen(Matrix a, Matrix b){
			//base case
			if(a.getRowDimension() == 1){
				double temp = a.get(0, 0)*b.get(0, 0);
				double [][] array = {{temp}};
				Matrix result = new Matrix(array);
				
				return result;
				
			
			} 
			//divide matrix into 4 parts
			
		
			Matrix A00 = a.getMatrix(0, (a.getColumnDimension()/2 -1), 0, (a.getColumnDimension()/2 -1));
			Matrix A10 = a.getMatrix(a.getColumnDimension()/2, (a.getColumnDimension() -1), 0, (a.getColumnDimension()/2 -1));
			Matrix A01 = a.getMatrix(0, (a.getColumnDimension()/2 -1), a.getColumnDimension()/2, (a.getColumnDimension()-1));
			Matrix A11 = a.getMatrix(a.getColumnDimension()/2, (a.getColumnDimension() -1), a.getColumnDimension()/2, (a.getColumnDimension()-1));
			
			
			Matrix B00 = b.getMatrix(0, (a.getColumnDimension()/2 -1), 0, (a.getColumnDimension()/2 -1));
			Matrix B10 = b.getMatrix(a.getColumnDimension()/2, (a.getColumnDimension() -1), 0, (a.getColumnDimension()/2 -1));
			Matrix B01 = b.getMatrix(0, (a.getColumnDimension()/2 -1), a.getColumnDimension()/2, (a.getColumnDimension()-1));
			Matrix B11 = b.getMatrix(a.getColumnDimension()/2, (a.getColumnDimension() -1), a.getColumnDimension()/2, (a.getColumnDimension()-1));
			
			//strassen adding
			Matrix m1 = strassen(A00.plus(A11),B00.plus(B11));
			Matrix m2 = strassen(A10.plus(A11),B00);
			Matrix m3 = strassen(A00,B01.minus(B11));
			Matrix m4 = strassen(A11,B10.minus(B00));
			Matrix m5 = strassen(A00.plus(A01),B11);
			Matrix m6 = strassen(A10.minus(A00),B00.plus(B01));
			Matrix m7 = strassen(A01.minus(A11),B10.plus(B11));
			
			Matrix C00 = m1.plus(m4).plus(m7).minus(m5);
			Matrix C01 = m3.plus(m5);
			Matrix C10 = m2.plus(m4);
			Matrix C11 = m1.plus(m3).minus(m2).plus(m6);
			
			Matrix C = new Matrix(a.getRowDimension(),a.getColumnDimension());
			
			C.setMatrix(0, (C.getRowDimension()/2 -1), 0, (C.getRowDimension()/2 -1), C00);
			C.setMatrix(0, (C.getRowDimension()/2 -1), C.getColumnDimension()/2, C.getColumnDimension() -1, C01);
			C.setMatrix(C.getRowDimension()/2, C.getRowDimension() -1, 0, (C.getColumnDimension()/2 -1), C10);
			C.setMatrix(C.getRowDimension()/2, C.getRowDimension() -1, C.getColumnDimension()/2, C.getColumnDimension() -1, C11);
			
			
					
			return C;
			
			
		}
		
			public boolean isPowerofTwo(int num){
				int square = 1;
				while(num >= square){
					if(num ==square){
						return true;
					}
					square = square*2;			
					
				}
					
				return false;
			}
		
		
			
		//while is not power of two
		public Matrix padding(Matrix a){
			
			int n = a.getColumnDimension();
			if(!isPowerofTwo(n)){
				while(!isPowerofTwo(n)){
					n++;
				}
				Matrix A = new Matrix(n,n);
			
				A.setMatrix(0, a.getColumnDimension()-1, 0, a.getColumnDimension()-1, a);
				return A;
			}else{
				return a;
			}
		}
		
		/** return a submatrix without any zeros
		 * 
		 * @param result
		 * @param matrix1
		 * @param matrix2
		 * @return
		 */
		public Matrix resultProcess(Matrix result, Matrix matrix1, Matrix matrix2){
			Matrix rs = result.getMatrix(0, matrix1.getColumnDimension()-1, 0, matrix2.getColumnDimension()-1);
			return rs;
			
		}
		

		/**
		 * @param args
		 */
		public static void main(String[] args) {
			// TODO Auto-generated method stub
		
			double[][] array = {{1,2,3,4,5},{5,6,7,8,9},{9,10,11,12,13},{12,13,14,15,16},{15,16,17,18,19}};
			double[][] array2 = {{4,5,6,7,8},{16,17,18,19,20},{21,22,24,25,26},{19,20,21,22,23},{29,30,31,110,111}};
			
//			double[][] array ={{1,2,3},{4,5,6},{7,8,9}};
//			double[][] array2 ={{1,2,3},{4,5,6},{7,8,9}};
			Matrix matrix1 = new Matrix(array);
			Matrix matrix2 = new Matrix(array2);
//			System.out.println(Arrays.deepToString(matrix1.getArray()));
//			System.out.println(Arrays.deepToString(matrix2.getArray()));
			
			
			Matrix matrix3 = matrix1.times(matrix2);
			System.out.println(Arrays.deepToString(matrix3.getArray()));
			
			StrassenMatrix test = new StrassenMatrix();
			
			Matrix m1 = test.padding(matrix1);
			Matrix m2 = test.padding(matrix2);
			Matrix result = test.strassen(m1, m2);
			
			result = test.resultProcess(result, matrix1, matrix2);
			
			System.out.println(Arrays.deepToString(result.getArray()));
		}

	
		}
	/**
	 * @param args
	 */



